// AVL.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>

typedef struct BinaryTreeNode {
    BinaryTreeNode* Parent;
    BinaryTreeNode* Left;
    BinaryTreeNode* Right;
    int Data;

    //相对高度, 左子树和右子树的最大高度 +1
    int Height;

public:
    BinaryTreeNode(BinaryTreeNode* parent, int data) :
        Parent(parent), Left(nullptr), Right(nullptr), Data(data), Height(1)
    {
    }
}TreeNode;

/*
* 计算节点相对高度
* 左子树和右子树的最大高度 +1
*/
int CalculateHeight(TreeNode* root) {
    if (root->Left == nullptr && root->Right == nullptr)
        return 1;

    if (root->Left == nullptr)
        return root->Right->Height + 1;

    if (root->Right == nullptr)
        return root->Left->Height + 1;

    return root->Left->Height > root->Right->Height ? root->Left->Height + 1 : root->Right->Height + 1;
}

/*
* 计算节点BF Balance Factor 平衡因子
* 左子树和右子树高度差
* 左子树高度 - 右子树高度的值
* 一般来说 BF 的绝对值大于 1，,平衡树二叉树就失衡，需要「旋转」纠正
*/
int CalculateBF(TreeNode* root) {
    if (root->Left == nullptr && root->Right == nullptr)
        return 0;

    if (root->Left == nullptr)
        return -root->Right->Height;

    if (root->Right == nullptr)
        return root->Left->Height;

    return root->Left->Height - root->Right->Height;
}

//左旋, 传入不平衡子树的根节点 (|BF| > 1)
TreeNode* LeftRotate(TreeNode* root) {
    TreeNode* oldRootNode = root;
    TreeNode* newRootNode = oldRootNode->Right;

    /*
    * 左旋, 将 右子树节点 作为 新的根节点
    * 将 新的根节点 的 左子树 作为 老的根节点 的 右子树
    * 老的根节点 作为 新的根节点 的 左子节点
    */
    oldRootNode->Right = newRootNode->Left;
    if (newRootNode->Left != nullptr)
        newRootNode->Left->Parent = oldRootNode;
    newRootNode->Left = oldRootNode;

    /*
    * 连接 父节点
    * 设置 新老根节点的父节点
    */
    newRootNode->Parent = oldRootNode->Parent;
    if (oldRootNode->Parent != nullptr)
        /*
        * 判断新节点是在父节点的左边还是右边
        */
        if (oldRootNode->Parent->Data > newRootNode->Data)
            oldRootNode->Parent->Left = newRootNode;

        else
            oldRootNode->Parent->Right = newRootNode;
    oldRootNode->Parent = newRootNode;

    //重新计算两个节点的 相对高度
    oldRootNode->Height = CalculateHeight(oldRootNode);
    newRootNode->Height = CalculateHeight(newRootNode);

    return newRootNode;
}

//右旋, 传入不平衡子树的根节点 (|BF| > 1)
TreeNode* RightRotate(TreeNode* root) {
    TreeNode* oldRootNode = root;
    TreeNode* newRootNode = oldRootNode->Left;

    /*
    * 右旋
    * 将 新的根节点 的 右子树 作为 旧的根节点 的 左子树
    * 老根节点 作为 新根节点 的 右子节点
    */
    oldRootNode->Left = newRootNode->Right;
    if (newRootNode->Right != nullptr)
        newRootNode->Right->Parent = oldRootNode;
    newRootNode->Right = oldRootNode;

    newRootNode->Parent = oldRootNode->Parent;
    if (oldRootNode->Parent != nullptr)
        if (oldRootNode->Parent->Data > newRootNode->Data)
            oldRootNode->Parent->Left = newRootNode;
        else
            oldRootNode->Parent->Right = newRootNode;
    oldRootNode->Parent = newRootNode;

    oldRootNode->Height = CalculateHeight(oldRootNode);
    newRootNode->Height = CalculateHeight(newRootNode);

    return newRootNode;
}

/*
* 旋转根节点的子树
*/
void RotateRoot(TreeNode*& root) {
    //更新高度
    root->Height = CalculateHeight(root);

    //计算 BF 平衡因子
    int rootBF = CalculateBF(root);

    /*
    * 旋转子树
    * 需要更新根节点
    */

    // L
    if (rootBF == 2) {
        //R
        if (CalculateBF(root->Left) == -1)
            //LR 型，左子树先左旋
            root->Left = LeftRotate(root->Left);
        root = RightRotate(root);
    }

    //R
    if (rootBF == -2) {
        //L
        if (CalculateBF(root->Right) == 1)
            //RL 型，右子树先右旋
            root->Right = RightRotate(root->Right);
        root = LeftRotate(root);
    }
}


/*
* 插入操作
* 递归插入新节点
* 刷新高度
*/
void InsertNode(TreeNode*& root, int data) {
    /*
    * 二叉排序树插入节点
    */
    if (root->Data > data) {
        if (root->Left != nullptr)
            InsertNode(root->Left, data);
        else
            root->Left = new TreeNode(root, data);
    }

    else {
        if (root->Right != nullptr)
            InsertNode(root->Right, data);
        else
            root->Right = new TreeNode(root, data);
    }

    RotateRoot(root);
}

/*
* 寻找前驱
*/
TreeNode* FindPrecursor(TreeNode* root) {
    /*
    * 1.左子树的最右节点
    */
    if (root->Left != nullptr) {
        root = root->Left;
        while (root->Right != nullptr)
            root = root->Right;
        return root;
    }
    
    else {
        /*
        * 2.为父节点的 右子节点, 结果为父节点
        */
        if (root->Parent->Right == root)
            return root->Parent;

        else {
            /*
            * 3.往上搜索, 直到该节点为父节点的右孩子, 结果为该节点的父节点
            */
            while (root->Parent != nullptr) {
                root = root->Parent;
                if (root->Parent->Right == root)
                    return root->Parent;
            }
            return root;
        }
    }
    
}

/*
* 寻找后继
*/
TreeNode* FindPosterior(TreeNode* root) {
    /*
    * 1.右子树的最左节点
    */
    if (root->Right != nullptr) {
        root = root->Right;
        while (root->Left != nullptr)
            root = root->Left;
        return root;
    }

    else {
        /*
        * 2.为父节点的 左子节点, 结果为父节点
        */
        if (root->Parent->Left == root)
            return root->Parent;

        else {
            /*
            * 3.往上搜索, 直到该节点为父节点的左孩子, 结果为该节点的父节点
            */
            while (root->Parent != nullptr) {
                root = root->Parent;
                if (root->Parent->Left == root)
                    return root->Parent;
            }
            return root;
        }
    }
}

/*
* 删除节点
*/
void DeleteNode(int data, TreeNode*& root) {
    if (root == nullptr)
        return;

    if (root->Data > data) {
        DeleteNode(data, root->Left);
        RotateRoot(root);
    }
        
    else if (root->Data < data) {
        DeleteNode(data, root->Right);
        RotateRoot(root);
    }

    else {
        /*
        * 1.被删除节点为叶子节点, 直接删除
        */
        if (root->Right == nullptr && root->Left == nullptr) {
            if (root->Parent->Left == root)
                root->Parent->Left = nullptr;
            else
                root->Parent->Right = nullptr;

            delete root;
        }

        /*
        * 2.被删除节点只含有一棵子树
        */
        //只包含左子树
        else if (root->Right == nullptr) {
            if (root->Parent->Left == root)
                root->Parent->Left = root->Left;
            else
                root->Parent->Right = root->Left;

            delete root;
        }
        //只包含右子树
        else if (root->Left == nullptr) {
            if (root->Parent->Left == root)
                root->Parent->Left = root->Right;
            else
                root->Parent->Right = root->Right;

            delete root;
        }

        /*
        * 3.包含两棵子树, 思路为使用 前驱 / 后继 节点进行替换
        */
        else {
            TreeNode* posterior = FindPosterior(root);

            //后继节点没有左子树, 只存在右子树
            if (posterior->Parent->Right == posterior)
                posterior->Parent->Right = posterior->Right;

            else
                posterior->Parent->Left = posterior->Right;

            posterior->Right->Parent = posterior->Parent;

            root->Data = posterior->Data;

            /*
            * 往上计算 parent 的高度, 直至 root
            */
            TreeNode* p = posterior->Parent;
            while (p != root) {
                p->Height = CalculateHeight(p);
            }

            delete posterior;
            
        }
    }
}

void InTravelBinaryTree(TreeNode* root) {
    if (root != nullptr) {
        InTravelBinaryTree(root->Left);
        std::cout << root->Data << " ";
        InTravelBinaryTree(root->Right);
    }
}

void PreTravelBinaryTree(TreeNode* root) {
    if (root != nullptr) {
        std::cout << root->Data << " ";
        PreTravelBinaryTree(root->Left);
        PreTravelBinaryTree(root->Right);
    }
}
int main()
{
    int data[] = { 3,2,1,4,5,6,7,10,9,8 };
    int data2[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    TreeNode* root = new TreeNode(nullptr, data2[0]);

    for (int i = 1; i < 10; i ++) {
        InsertNode(root, data2[i]);
    }

    DeleteNode(8, root);
    DeleteNode(5, root);
    DeleteNode(7, root);

    InTravelBinaryTree(root);
    std::cout << std::endl;

    PreTravelBinaryTree(root);
    std::cout << std::endl;
}